We investigate two closely related LZ78-based compression schemes: LZMW (an old scheme by Miller and Wegman) and LZD (a recent variant by Goto et al.). Both LZD and LZMW naturally produce a grammar for a string of length n; we show that the size of this grammar can be larger than the size of the smallest grammar by a factor Ω(n13)Ω(n13) but is always within a factor O((nlogn)23)O((nlogn)23) . In addition, we show that the standard algorithms using Θ(z)Θ(z) working space to construct the LZD and LZMW parsings, where z is the size of the parsing, work in Ω(n54)Ω(n54) time in the worst case. We then describe a new Las Vegas LZD/LZMW parsing algorithm that uses O(zlogn)O(zlogn) space and O(n+zlog2n)O(n+zlog2n) time w.h.p.
展开▼
